home *** CD-ROM | disk | FTP | other *** search
/ Qoole for Quake / Qoole for Quake (USA) / Qoole for Quake (USA).bin / Tutorial / HTML / QUBE.ZIP / SRC / FLOW.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-05  |  10.9 KB  |  495 lines
  1. #include "vis.h"
  2. #include "curs.h"
  3.  
  4. int        c_chains;
  5. int        c_portalskip, c_leafskip;
  6. int        c_vistest, c_mighttest;
  7.  
  8. int        active;
  9.  
  10. void CheckStack (leaf_t *leaf, threaddata_t *thread)
  11. {
  12.     pstack_t    *p;
  13.  
  14.     for (p=thread->pstack_head.next ; p ; p=p->next)
  15.         if (p->leaf == leaf)
  16.             Error ("CheckStack: leaf recursion");
  17. }
  18.  
  19.  
  20. /*
  21. ==============
  22. ClipToSeperators
  23.  
  24. Source, pass, and target are an ordering of portals.
  25.  
  26. Generates seperating planes canidates by taking two points from source and one
  27. point from pass, and clips target by them.
  28.  
  29. If target is totally clipped away, that portal can not be seen through.
  30.  
  31. Normal clip keeps target on the same side as pass, which is correct if the
  32. order goes source, pass, target.  If the order goes pass, source, target then
  33. flipclip should be set.
  34. ==============
  35. */
  36. winding_t    *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip)
  37. {
  38.     int            i, j, k, l;
  39.     plane_t        plane;
  40.     vec3_t        v1, v2;
  41.     float        d;
  42.     double        length;
  43.     int            counts[3];
  44.     qboolean        fliptest;
  45.  
  46. /* check all combinations     */
  47.     for (i=0 ; i<source->numpoints ; i++)
  48.     {
  49.         l = (i+1)%source->numpoints;
  50.         VectorSubtract (source->points[l] , source->points[i], v1);
  51.  
  52.     /* fing a vertex of pass that makes a plane that puts all of the */
  53.     /* vertexes of pass on the front side and all of the vertexes of */
  54.     /* source on the back side */
  55.         for (j=0 ; j<pass->numpoints ; j++)
  56.         {
  57.             VectorSubtract (pass->points[j], source->points[i], v2);
  58.  
  59.             plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
  60.             plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
  61.             plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
  62.             
  63.         /* if points don't make a valid plane, skip it */
  64.  
  65.             length = plane.normal[0] * plane.normal[0]
  66.             + plane.normal[1] * plane.normal[1]
  67.             + plane.normal[2] * plane.normal[2];
  68.             
  69.             if (length < ON_EPSILON)
  70.                 continue;
  71.  
  72.             length = 1/sqrt(length);
  73.             
  74.             plane.normal[0] *= length;
  75.             plane.normal[1] *= length;
  76.             plane.normal[2] *= length;
  77.  
  78.             plane.dist = DotProduct (pass->points[j], plane.normal);
  79.  
  80.         /* */
  81.         /* find out which side of the generated seperating plane has the */
  82.         /* source portal */
  83.         /* */
  84.             fliptest = false;
  85.             for (k=0 ; k<source->numpoints ; k++)
  86.             {
  87.                 if (k == i || k == l)
  88.                     continue;
  89.                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
  90.                 if (d < -ON_EPSILON)
  91.                 {    /* source is on the negative side, so we want all */
  92.                     /* pass and target on the positive side */
  93.                     fliptest = false;
  94.                     break;
  95.                 }
  96.                 else if (d > ON_EPSILON)
  97.                 {    /* source is on the positive side, so we want all */
  98.                     /* pass and target on the negative side */
  99.                     fliptest = true;
  100.                     break;
  101.                 }
  102.             }
  103.             if (k == source->numpoints)
  104.                 continue;        /* planar with source portal */
  105.  
  106.         /* */
  107.         /* flip the normal if the source portal is backwards */
  108.         /* */
  109.             if (fliptest)
  110.             {
  111.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  112.                 plane.dist = -plane.dist;
  113.             }
  114.             
  115.         /* */
  116.         /* if all of the pass portal points are now on the positive side, */
  117.         /* this is the seperating plane */
  118.         /* */
  119.             counts[0] = counts[1] = counts[2] = 0;
  120.             for (k=0 ; k<pass->numpoints ; k++)
  121.             {
  122.                 if (k==j)
  123.                     continue;
  124.                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  125.                 if (d < -ON_EPSILON)
  126.                     break;
  127.                 else if (d > ON_EPSILON)
  128.                     counts[0]++;
  129.                 else
  130.                     counts[2]++;
  131.             }
  132.             if (k != pass->numpoints)
  133.                 continue;    /* points on negative side, not a seperating plane */
  134.                 
  135.             if (!counts[0])
  136.             {
  137.                 continue;    /* planar with seperating plane */
  138.             }
  139.         
  140.         /* */
  141.         /* flip the normal if we want the back side */
  142.         /* */
  143.             if (flipclip)
  144.             {
  145.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  146.                 plane.dist = -plane.dist;
  147.             }
  148.             
  149.         /* */
  150.         /* clip target by the seperating plane */
  151.         /* */
  152.             target = ClipWinding (target, &plane, false);
  153.             if (!target)
  154.                 return NULL;        /* target is not visible */
  155.         }
  156.     }
  157.     
  158.     return target;
  159. }
  160.  
  161.  
  162.  
  163. /*
  164. ==================
  165. RecursiveLeafFlow
  166.  
  167. Flood fill through the leafs
  168. If src_portal is NULL, this is the originating leaf
  169. ==================
  170. */
  171. void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
  172. {
  173.     pstack_t    stack;
  174.     portal_t    *p;
  175.     plane_t        backplane;
  176.     winding_t    *source, *target;
  177.     leaf_t         *leaf;
  178.     int            i, j;
  179.     long        *test, *might, *vis;
  180.     qboolean        more;
  181.     
  182.     c_chains++;
  183.  
  184.     leaf = &leafs[leafnum];
  185.     CheckStack (leaf, thread);
  186.     
  187. /* mark the leaf as visible */
  188.     if (! (thread->leafvis[leafnum>>3] & (1<<(leafnum&7)) ) )
  189.     {
  190.         thread->leafvis[leafnum>>3] |= 1<<(leafnum&7);
  191.         thread->base->numcansee++;
  192.     }
  193.     
  194.     prevstack->next = &stack;
  195.     stack.next = NULL;
  196.     stack.leaf = leaf;
  197.     stack.portal = NULL;
  198.     stack.mightsee = malloc(bitbytes);
  199.     might = (long *)stack.mightsee;
  200.     vis = (long *)thread->leafvis;
  201.     
  202. /* check all portals for flowing into other leafs     */
  203.     for (i=0 ; i<leaf->numportals ; i++)
  204.     {
  205.         p = leaf->portals[i];
  206.  
  207.         if ( ! (prevstack->mightsee[p->leaf>>3] & (1<<(p->leaf&7)) ) )
  208.         {
  209.             c_leafskip++;
  210.             continue;    /* can't possibly see it */
  211.         }
  212.  
  213.     /* if the portal can't see anything we haven't allready seen, skip it */
  214.         if (p->status == stat_done)
  215.         {
  216.             c_vistest++;
  217.             test = (long *)p->visbits;
  218.         }
  219.         else
  220.         {
  221.             c_mighttest++;
  222.             test = (long *)p->mightsee;
  223.         }
  224.         more = false;
  225.         for (j=0 ; j<bitlongs ; j++)
  226.         {
  227.             might[j] = ((long *)prevstack->mightsee)[j] & test[j];
  228.             if (might[j] & ~vis[j])
  229.                 more = true;
  230.         }
  231.         
  232.         if (!more)
  233.         {    /* can't see anything new */
  234.             c_portalskip++;
  235.             continue;
  236.         }
  237.         
  238. /* get plane of portal, point normal into the neighbor leaf */
  239.         stack.portalplane = p->plane;
  240.         VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
  241.         backplane.dist = -p->plane.dist;
  242.             
  243.         if (VectorCompare (prevstack->portalplane.normal, backplane.normal) )
  244.             continue;    /* can't go out a coplanar face */
  245.     
  246.         c_portalcheck++;
  247.         
  248.         stack.portal = p;
  249.         stack.next = NULL;
  250.         
  251.         target = ClipWinding (p->winding, &thread->pstack_head.portalplane, false);
  252.         if (!target)
  253.             continue;
  254.             
  255.         if (!prevstack->pass)
  256.         {    /* the second leaf can only be blocked if coplanar */
  257.         
  258.             stack.source = prevstack->source;
  259.             stack.pass = target;
  260.             RecursiveLeafFlow (p->leaf, thread, &stack);
  261.             FreeWinding (target);
  262.             continue;
  263.         }
  264.  
  265.         target = ClipWinding (target, &prevstack->portalplane, false);
  266.         if (!target)
  267.             continue;
  268.         
  269.         source = CopyWinding (prevstack->source);
  270.  
  271.         source = ClipWinding (source, &backplane, false);
  272.         if (!source)
  273.         {
  274.             FreeWinding (target);
  275.             continue;
  276.         }
  277.  
  278.         c_portaltest++;
  279.  
  280.         if (testlevel > 0)
  281.         {
  282.             target = ClipToSeperators (source, prevstack->pass, target, false);
  283.             if (!target)
  284.             {
  285.                 FreeWinding (source);
  286.                 continue;
  287.             }
  288.         }
  289.         
  290.         if (testlevel > 1)
  291.         {
  292.             target = ClipToSeperators (prevstack->pass, source, target, true);
  293.             if (!target)
  294.             {
  295.                 FreeWinding (source);
  296.                 continue;
  297.             }
  298.         }
  299.         
  300.         if (testlevel > 2)
  301.         {
  302.             source = ClipToSeperators (target, prevstack->pass, source, false);
  303.             if (!source)
  304.             {
  305.                 FreeWinding (target);
  306.                 continue;
  307.             }
  308.         }
  309.         
  310.         if (testlevel > 3)
  311.         {
  312.             source = ClipToSeperators (prevstack->pass, target, source, true);
  313.             if (!source)
  314.             {
  315.                 FreeWinding (target);
  316.                 continue;
  317.             }
  318.         }
  319.  
  320.         stack.source = source;
  321.         stack.pass = target;
  322.  
  323.         c_portalpass++;
  324.     
  325.     /* flow through it for real */
  326.         RecursiveLeafFlow (p->leaf, thread, &stack);
  327.         
  328.         FreeWinding (source);
  329.         FreeWinding (target);
  330.     }
  331.     
  332.     free (stack.mightsee);
  333. }
  334.  
  335.  
  336. /*
  337. ===============
  338. PortalFlow
  339.  
  340. ===============
  341. */
  342. void PortalFlow (portal_t *p)
  343. {
  344.     threaddata_t    data;
  345.  
  346.     if (p->status != stat_working)
  347.         Error ("PortalFlow: reflowed");
  348.     p->status = stat_working;
  349.     
  350.     p->visbits = malloc (bitbytes);
  351.     memset (p->visbits, 0, bitbytes);
  352.  
  353.     memset (&data, 0, sizeof(data));
  354.     data.leafvis = p->visbits;
  355.     data.base = p;
  356.     
  357.     data.pstack_head.portal = p;
  358.     data.pstack_head.source = p->winding;
  359.     data.pstack_head.portalplane = p->plane;
  360.     data.pstack_head.mightsee = p->mightsee;
  361.         
  362.     RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
  363.  
  364.     p->status = stat_done;
  365. }
  366.  
  367.  
  368. /*
  369. ===============================================================================
  370.  
  371. This is a rough first-order aproximation that is used to trivially reject some
  372. of the final calculations.
  373.  
  374. ===============================================================================
  375. */
  376.  
  377. byte    portalsee[MAX_PORTALS];
  378. int        c_leafsee, c_portalsee;
  379.  
  380. void SimpleFlood (portal_t *srcportal, int leafnum)
  381. {
  382.     int        i;
  383.     leaf_t    *leaf;
  384.     portal_t    *p;
  385.     
  386.     if (srcportal->mightsee[leafnum>>3] & (1<<(leafnum&7)) )
  387.         return;
  388.     srcportal->mightsee[leafnum>>3] |= (1<<(leafnum&7));
  389.     c_leafsee++;
  390.     
  391.     leaf = &leafs[leafnum];
  392.     
  393.     for (i=0 ; i<leaf->numportals ; i++)
  394.     {
  395.         p = leaf->portals[i];
  396.         if ( !portalsee[ p - portals ] )
  397.             continue;
  398.         SimpleFlood (srcportal, p->leaf);
  399.     }
  400. }
  401.  
  402.  
  403. /*
  404. ==============
  405. BasePortalVis
  406. ==============
  407. */
  408. void BasePortalVis (void)
  409. {
  410.     int            i, j, k;
  411.     portal_t    *tp, *p;
  412.     float        d;
  413.     winding_t    *w;
  414.     int        portalcount = numportals*2;
  415.  
  416.     ShowStatusEntry("Calculating basic portal vis.");
  417.     ShowTempEntry("%d portals to vis.", portalcount);
  418.         
  419.     MoveCurs(4, 17);
  420.     CPrintf("$b4$f6"
  421.         "$f3-----------------------------" "$n"
  422.         "  $f6Portal $f2    0$f6 of $f2    0$f6  " "$n"
  423.         "    Portal number:    $f2    0$f6  " "$n"
  424.         "    Portal might see: $f2    0$f6  ");
  425.  
  426.     MoveCurs(23, 18);
  427.     CPrintf("$f2%5i", numportals*2);
  428.  
  429.         for (i=0, p = portals ; i<portalcount ; i++, p++)
  430.     {
  431.         PercentBar(i*256/portalcount);
  432.         SetForeColor(ANSI_GREEN);
  433.         SetBackColor(ANSI_BLUE);
  434.         MoveCurs(13, 18);
  435.         CPrintf("%5i", i);
  436.  
  437.         p->mightsee = malloc (bitbytes);
  438.         memset (p->mightsee, 0, bitbytes);
  439.         
  440.         c_portalsee = 0;
  441.         memset (portalsee, 0, portalcount);
  442.  
  443.         for (j=0, tp = portals ; j<portalcount ; j++, tp++)
  444.         {
  445.             if (j == i)
  446.                 continue;
  447.             w = tp->winding;
  448.             for (k=0 ; k<w->numpoints ; k++)
  449.             {
  450.                 d = DotProduct (w->points[k], p->plane.normal)
  451.                     - p->plane.dist;
  452.                 if (d > ON_EPSILON)
  453.                     break;
  454.             }
  455.             if (k == w->numpoints)
  456.                 continue;    /* no points on front */
  457.                 
  458.             
  459.             w = p->winding;
  460.             for (k=0 ; k<w->numpoints ; k++)
  461.             {
  462.                 d = DotProduct (w->points[k], tp->plane.normal)
  463.                     - tp->plane.dist;
  464.                 if (d < -ON_EPSILON)
  465.                     break;
  466.             }
  467.             if (k == w->numpoints)
  468.                 continue;    /* no points on front */
  469.  
  470.             portalsee[j] = 1;        
  471.             c_portalsee++;
  472.             
  473.         }
  474.         
  475.         c_leafsee = 0;
  476.         SimpleFlood (p, p->leaf);
  477.         p->nummightsee = c_leafsee;
  478. /*        printf ("portal:%4i  c_leafsee:%4i \n", i, c_leafsee); */
  479.  
  480.                 MoveCurs(26, 19);
  481.         CPrintf("%5i$n%5i", (int)(p - portals), p->nummightsee);
  482.         
  483.     }
  484.  
  485.         MoveCurs(4, 17);
  486.     CPrintf("$b4$f6"
  487.         "                             $n"
  488.         "                             $n"
  489.         "                             $n"
  490.         "                             ");
  491.  
  492.     ShowTempEntry("Basic portal vis complete.");
  493. }
  494.  
  495.